package cn.edu.jxau.test;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {

		int[] arr = new int[] { 7, 5, 6, 4 };
		System.out.println(sort(arr));
	}

	public static int sort(int[] arr) {

		int[] aux = new int[arr.length];
		return sort(arr, aux, 0, arr.length - 1);
	}

	private static int sort(int[] arr, int[] aux, int low, int high) {

		int count = 0;
		if (low >= high) {
			return count;
		}
		int mid = low + ((high - low) >> 1);
		count += sort(arr, aux, low, mid);
		count += sort(arr, aux, mid + 1, high);
		count += merge(arr, aux, low, mid, high);
		return count;
	}

	private static int merge(int[] arr, int[] aux, int low, int mid, int high) {

		int count = 0;
		int i = low;
		int j = mid + 1;
		for (int k = low; k <= high; k++) {
			aux[k] = arr[k];
		}
		int k = low;
		while (i <= mid && j <= high) {
			if (aux[i] < aux[j]) {
				arr[k++] = aux[i++];
			} else {
				arr[k++] = aux[j++];
				count += (i - low + 1);
			}
		}
		while (i <= mid) {
			arr[k++] = aux[i++];
		}
		while (j <= high) {
			arr[k++] = aux[j++];
		}
		return count;
	}
}
